package 力扣;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @author yyq
 * @create 2022-03-31 8:52
 */
public class leetcode239 {
    public static void main(String[] args) {
        int[] ints = maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
        System.out.println(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3));
    }
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] maxs = new int[nums.length-k+1];
        YYQQueue deque = new YYQQueue();
        if(nums.length<=k){
            Arrays.sort(nums);
            return new int[]{nums[nums.length-1]};
        }
        if(nums.length>k){
            // 初始化队列
            for (int i = 0; i < k; i++) {
                deque.push(nums[i]);
            }

            int prepoint = k-1; //指向当前窗口最后一个
            int backpoint = 0;  //指向当前窗口第一个
            while(prepoint<nums.length){
                maxs[backpoint] = deque.getMax();
                deque.pop(nums[backpoint]);
                if(prepoint+1 == nums.length) break;
                deque.push(nums[prepoint+1]);
                prepoint++;
                backpoint++;
            }

        }
        return maxs;
    }


}

class YYQQueue{
    Deque<Integer> deque;


    public YYQQueue() {
        deque=new LinkedList<>();
    }

    // push到尾端
    //      如果小于尾端数据直接进
    //      如果大于尾端数据，pop出尾端数据，直到它小于尾端数据或者它作为头端数据
    public void push(int num){
        if (deque.isEmpty()){
            deque.add(num);
            return;
        }
        if(num<=deque.getLast()){
            deque.addLast(num);
        }else {
            while(num>deque.getLast()){

                deque.pollLast();
                if (deque.isEmpty()) {
                    deque.add(num);
                    return;
                }
            }
            deque.add(num);
        }

    }
    // pop一个数 如果它等于开端数据 pop开端数据，如果不是开端数据不用管
    public void pop(int num){
        if (deque.getFirst()==num) {
            deque.pollFirst();
        }
    }

    public int getMax(){
        return deque.peek();
    }
}
